package sort;

import java.util.HashMap;
import java.util.Map;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/26 11:30
 * @description:  和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1
 * 现在给定一个整数数组nums，在所有可能的子序列中找到最长的和谐子序列的长度
 */
public class FindLHS {
    //实际就是找 x和x+1的个数
    public int findLHS(int[] nums) {

        int ret = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0));
        }
        for(int key:map.keySet()){
            if(map.containsKey(key+1)){
                ret = Math.max(ret,map.get(key)+map.get(key+1));
            }
        }
        return ret;
    }
}
